#include <iostream>
#include <vector>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include "BinarySearchTree.h"
using namespace std;

template <typename T>
void BST_sort(std::vector<T> &_data)
{
    vector<T> ret;
    BinarySearchTree<T> bst;
    for(size_t i = 0; i<_data.size();i++)       
    {
        bst.insert(_data[i]);           //数据插入
    }
    bst.InorderTravesal(ret);           //中序遍历到ret中
    if(_data.size() != ret.size()) 
    {
        std::cout<<"error size";        //防止出错
        return;
    }
    std::cout<<"中序遍历的输出结果是："<<std::endl;
    for(size_t i = 0; i<ret.size();i++) //向量拷贝
    {
        _data[i]=ret[i];
        std::cout<<_data[i]<<"  ";
    }
    std::cout<<std::endl<<std::endl;
}

template <typename T>
void Randomized_BST_sort(std::vector<T> &_data)
{
    T middle;
    size_t tmp;
    unsigned seed;
    seed = time(0);
    srand(seed);
    for(size_t i = 0; i<_data.size();i++)
    {
        tmp = rand()%_data.size();
        middle = _data[i];
        _data[i] = _data[tmp];
        _data[tmp] = middle;
    }
    std::cout<<"打乱顺序后的向量次序为："<<std::endl;
    for(size_t i = 0; i<_data.size();i++) 
    {
        std::cout<<_data[i]<<"  ";
    }
    std::cout<<std::endl<<std::endl;
    BST_sort(_data);
}

    // Test program
int main( )
{
    vector<int> vec1 = {5,1,4,3,9,2,6,7,8};
    vector<float> vec2 = {1.1,2.2,3.3,4.4,5.5,6.6,7.7,8.8,9.9};
    
    std::cout<<"原始向量1为：（二叉搜索树中序遍历）"<<std::endl;
    for(size_t i = 0; i<vec1.size();i++) {std::cout<<vec1[i]<<"  ";}
    std::cout<<std::endl<<std::endl;
    BST_sort(vec1);

    std::cout<<"原始向量2为：（乱序二叉搜索树中序遍历）"<<std::endl;
    for(size_t i = 0; i<vec2.size();i++) {std::cout<<vec2[i]<<"  ";}
    std::cout<<std::endl<<std::endl;
    Randomized_BST_sort(vec2);

    return 0;
}



/*
    BinarySearchTree<int> t;
    int NUMS = 400000;
    const int GAP  =   3711;
    int i;

    cout << "Checking... (no more output means success)" << endl;

    for( i = GAP; i != 0; i = ( i + GAP ) % NUMS )
        t.insert( i );

    for( i = 1; i < NUMS; i+= 2 )
        t.remove( i );

    if( NUMS < 40 )
        t.printTree( );
    if( t.findMin( ) != 2 || t.findMax( ) != NUMS - 2 )
        cout << "FindMin or FindMax error!" << endl;

    for( i = 2; i < NUMS; i+=2 )
        if( !t.contains( i ) )
            cout << "Find error1!" << endl;

    for( i = 1; i < NUMS; i+=2 )
    {
        if( t.contains( i ) )
            cout << "Find error2!" << endl;
    }

    BinarySearchTree<int> t2;
    t2 = t;

    for( i = 2; i < NUMS; i+=2 )
        if( !t2.contains( i ) )
            cout << "Find error1!" << endl;

    for( i = 1; i < NUMS; i+=2 )
    {
        if( t2.contains( i ) )
            cout << "Find error2!" << endl;
    }

    cout << "Finished testing" << endl;
    */
